#include "main/utils.h"
using namespace std;

int subSeqNum1(const string& s, const string& t) {
  int s_len = s.size();
  int t_len = t.size();
  vector<vector<int>> dp;
  dp.resize(s_len + 1);
  for (int i = 0; i < s_len + 1; ++i) {
    dp[i].resize(t_len + 1, 0);
  }
  dp[0][0] = 1;
  for (int i = 0; i < s_len; ++i) {
    dp[i + 1][0] = 1;
    for (int j = 0; j <= i && j < t_len; ++j) {
      if (s[i] == t[j]) {
        dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
      } else {
        dp[i + 1][j + 1] = dp[i][j + 1];
      }
    }
  }

  return dp[s_len][t_len];
}

int subSeqNum2(const string& s, const string& t) {
  int s_len = s.size();
  int t_len = t.size();
  vector<vector<int>> dp;
  dp.resize(2);
  for (int i = 0; i < 2; ++i) {
    dp[i].resize(t_len + 1, 0);
  }
  dp[0][0] = 1;
  for (int i = 0; i < s_len; ++i) {
    dp[(i + 1) % 2][0] = 1;
    for (int j = 0; j <= i && j < t_len; ++j) {
      if (s[i] == t[j]) {
        dp[(i + 1) % 2][j + 1] = dp[i % 2][j] + dp[i % 2][j + 1];
      } else {
        dp[(i + 1) % 2][j + 1] = dp[i % 2][j + 1];
      }
    }
  }

  return dp[s_len % 2][t_len];
}

int subSeqNum3(const string& s, const string& t) {
  int s_len = s.size();
  int t_len = t.size();
  vector<int> dp(t_len + 1, 0);
  for (int i = 0; i < s_len; ++i) {
    dp[0] = 1;
    int pre = 1;
    for (int j = 0; j <= i && j < t_len; ++j) {
      int cur;
      if (s[i] == t[j]) {
        cur = pre + dp[j + 1];
      } else {
        cur = dp[j + 1];
      }
      pre = dp[j + 1];
      dp[j + 1] = cur;
    }
  }

  return dp[t_len];
}

int subSeqNum4(const string& s, const string& t) {
  int s_len = s.size();
  int t_len = t.size();
  vector<int> dp(t_len + 1, 0);
  dp[0] = 1;
  for (int i = 0; i < s_len; ++i) {
    for (int j = min(i, t_len - 1); j >= 0; --j) {
      if (s[i] == t[j]) {
        dp[j + 1] = dp[j] + dp[j + 1];
      }
    }
  }

  return dp[t_len];
}

int main() {
  string s = "appplep";
  string t = "apple";
  cout << subSeqNum1(s, t) << endl;
  cout << subSeqNum2(s, t) << endl;
  cout << subSeqNum3(s, t) << endl;
  cout << subSeqNum4(s, t) << endl;

  return 0;
}
